//Saturday, December 05 2009
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAXN = 20, MAXK = 130;
const string MATCHES [10] =
{
	"1110111",
	"0010011",
	"1011101",
	"1011011",
	"0111010",
	"1101011",
	"1101111",
	"1010010",
	"1111111",
	"1111011"
};
int N, K, digit [MAXN];
long long dp [MAXN][MAXK][MAXK];

class NumbersAndMatches
{
public:
	long long differentNumbers(long long NN, int KK)
	{
		N = 0;
		K = KK;
		while(NN > 0)
		{
			digit[N++] = NN%10;
			NN /= 10;
		}
		memset(dp, -1, sizeof(dp));
		return solve(0,0,0);
	}

	//n: number of positions;
	//add: matches needed to be added;
	//rem: matches needed to be removed;
	long long solve(int n, int add, int rem)
	{
		if(add>K || rem>K)
			return 0;
		if(n == N)
			return add == rem ? 1 : 0;
		if(dp[n][add][rem] != -1)
			return dp[n][add][rem];
		long long &sol = dp [n][add][rem] = 0;
		for(int d=0; d<10; d++)
		{
			int ad = 0;
			int rm = 0;
			for(int i=0; i<7; i++)
			{
				if (MATCHES [digit [n]][i] == '0' && MATCHES [d][i] == '1')
					ad++;
				else if (MATCHES [digit [n]][i] == '1' && MATCHES [d][i] == '0')
					rm++;
			}
			sol += solve(n+1, add+ad, rem+rm);
		}
		return sol;
	}
};
